In many structured prediction problems, complex relationships between variables are compactly defined using graphical structures. The most prevalent graphical prediction methods---probabilistic graphical models and large margin methods---have their own distinct strengths but also possess significant drawbacks. Conditional random fields (CRFs) are Fisher consistent, but they do not permit integration of customized loss metrics into their learning process. Large-margin models, such as structured support vector machines (SSVMs), have the flexibility to incorporate customized loss metrics, but lack Fisher consistency guarantees. We present adversarial graphical models (AGM), a distributionally robust approach for constructing a predictor that performs robustly for a class of data distributions defined using a graphical structure. Our approach enjoys both the flexibility of incorporating customized loss metrics into its design as well as the statistical guarantee of Fisher consistency. We present exact learning and prediction algorithms for AGM with time complexity similar to existing graphical models and show the practical benefits of our approach with experiments.

Distributionally Robust Graphical Models The authors suggest dealing with the structure prediction task using adversarial graphical model (AGM), a generative model trained using an adversary distribution, instead of the empirical one. Instead of focusing on the loss metric, the authors focus on the graphical model allowing more flexibility wrt the loss metric. The AGM algorithm has similar complexity to conditional random fields but is less limited in its loss metric and is Fisher consistent for additive loss metrics. Following a complex mathematical transformation, the authors provide optimization of node and edge distribution of the graphical model but since this optimization is intractable, they restrict their method to tree-structural models or models with low treewidths. I would expect the authors to discuss this limitation of their algorithm.

In many structured prediction problems, complex relationships between variables are compactly defined using graphical structures. The most prevalent graphical prediction methods---probabilistic graphical models and large margin methods---have their own distinct strengths but also possess significant drawbacks. Conditional random fields (CRFs) are Fisher consistent, but they do not permit integration of customized loss metrics into their learning process. Large-margin models, such as structured support vector machines (SSVMs), have the flexibility to incorporate customized loss metrics, but lack Fisher consistency guarantees. We present adversarial graphical models (AGM), a distributionally robust approach for constructing a predictor that performs robustly for a class of data distributions defined using a graphical structure.